package com.cn.algorithm.one.tree;


import com.cn.algorithm.one.printer.BinaryTreeInfo;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class BinaryTree<E> implements BinaryTreeInfo {

    int size;

    Node<E> root;

    public void preorder(VisitorTree<E> visitorTree) {
        if (visitorTree == null) {
            return;
        }
        preorder(visitorTree, root);
    }

    public void preorder(VisitorTree<E> visitor, Node<E> node) {
        if (node == null || visitor.stop) {
            return;
        }
        visitor.stop = visitor.visit(node.element);
        preorder(visitor, node.left);
        preorder(visitor, node.right);
    }

    public void preorder1(VisitorTree<E> visitor) {
        if (visitor == null || root == null) {
            return;
        }
        Node<E> node = root;
        Stack<Node<E>> stack = new Stack<>();
        while (true) {
            if (node != null) {
                if (visitor.stop) {
                    return;
                }
                visitor.stop = visitor.visit(node.element);
                if (node.right != null) {
                    stack.push(node.right);
                }
                node = node.left;
            } else if (stack.isEmpty()) {
                return;
            } else {
                node = stack.pop();

            }
        }
    }

    public void inorder(VisitorTree<E> visitor) {
        if (visitor == null) {
            return;
        }
        inorder(visitor, root);
    }

    public void inorder(VisitorTree<E> visitor, Node<E> node) {
        if (node == null || visitor.stop) {
            return;
        }
        inorder(visitor, node.left);
        if (visitor.stop) {
            return;
        }
        visitor.stop = visitor.visit(node.element);
        inorder(visitor, node.right);
    }

    public void inorder1(VisitorTree<E> visitor) {
        if (visitor == null || root == null) {
            return;
        }
        Node<E> node = root;
        Stack<Node<E>> stack = new Stack<>();
        while (true) {
            if (node != null) {
                stack.push(node);
                node = node.left;
            } else if (stack.isEmpty()) {
                return;
            } else {
                node = stack.pop();
                if (visitor.stop) {
                    return;
                }
                visitor.stop = visitor.visit(node.element);
                node = node.right;
            }
        }
    }

    public void postorder(VisitorTree<E> visitor) {
        if (visitor == null) {
            return;
        }
    }

    public void postorder(VisitorTree<E> visitor, Node<E> node) {
        if (node == null || visitor.stop) {
            return;
        }
        postorder(visitor, node.left);
        postorder(visitor, node.right);
        if (visitor.stop) {
            return;
        }
        visitor.stop = visitor.visit(node.element);
    }

    public void levelOrder(VisitorTree<E> visitor) {
        if (visitor == null || root == null) {
            return;
        }
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            if (visitor.stop){
                return;
            }
            visitor.stop = visitor.visit(node.element);
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }

    public int height() {
        if (root == null) {
            return 0;
        }
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        int height = 0;
        int levelCount = 1;
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            levelCount--;
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
            if (levelCount == 0) {
                height++;
                levelCount = queue.size();
            }
        }
        return height;
    }

    public boolean isCompleteTree() {
        if (root == null) {
            return false;
        }
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        boolean isLeaf = false;
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            if (isLeaf && !node.isLeafNode()) {
                return false;
            }
            if (node.left != null) {
                queue.offer(node.left);
            } else if (node.right != null) {
                return false;
            }
            if (node.right != null) {
                queue.offer(node.right);
            } else {
                isLeaf = true;
            }

        }
        return true;
    }

    public Node<E> predecessor(Node<E> node) {
        if (node == null) {
            return null;
        }
        Node<E> left = node.left;
        if (left != null) {
            while (left.right != null) {
                left = left.right;
            }
            return left;
        }
        while (node.parent != null && node.isLeftChild()) {
            node = node.parent;
        }
        return node.parent;
    }

    public Node<E> successor(Node<E> node) {
        if (node == null) {
            return null;
        }
        Node<E> right = node.right;
        if (right != null) {
            while (right.left != null) {
                right = right.left;
            }
            return right;
        }
        while (node.parent != null && node.isRightChild()) {
            node = node.parent;
        }
        return node.parent;
    }

    public static class Node<E> {

        E element;

        Node<E> parent;

        Node<E> left;

        Node<E> right;

        public Node(E element, Node<E> parent) {
            this.element = element;
            this.parent = parent;
        }

        public boolean isLeftChild() {
            return parent != null && this == parent.left;
        }

        public boolean isRightChild() {
            return parent != null && this == parent.right;
        }

        public boolean hasTwoChildren() {
            return left != null && right != null;
        }

        public boolean isLeafNode() {
            return left == null && right == null;
        }

        public Node<E> sibling() {
            if (parent == null) {
                return null;
            } else if (this.isLeftChild()) {
                return parent.right;
            } else {
                return parent.left;
            }
        }
    }

    @Override
    public Object root() {
        return root;
    }

    @Override
    public Object left(Object node) {
        return ((Node<E>)node).left;
    }

    @Override
    public Object right(Object node) {
        return ((Node<E>)node).right;
    }

    @Override
    public Object string(Object node) {
        Node<E> myNode = (Node<E>)node;
        String parentString = "null";
        if (myNode.parent != null) {
            parentString = myNode.parent.element.toString();
        }
        return myNode.element + "_p(" + parentString + ")";
    }
}
